
#define _BSD_SOURCE
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <errno.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/mman.h>

#include "config.h"

#include "zbd-cache.h"
#include "log.h"
#include "hashtable.h"
#include "timerUtils.h"

#include "../algorithms-general.h"

#define MAXTRACEMAPLEN 2000000000
int MaxLevel = 0;
/* zbd-cache.h */
struct cache_page;
extern struct zbd_zone *zones_collection;
extern struct cache_runtime cache_rt;

extern int RMW(uint32_t zoneId, uint64_t from_blk, uint64_t to_blk);

/* most-specified objs */
struct page_payload
{
    uint64_t checked_round; // Abort 弃用
};

static uint64_t global_evic_round;

/* cache out */
static int zoneopt_get_zone_out();
static int compareByReleaseForMiss(const void *a, const void *b);

struct zoneFutureStat
{
    int zoneId;
    int releaseCnt;
    int releaseForMiss;
    struct zoneFutureStat *pre, *next;

    int increamentalBlks;
};

struct zfsIndex
{
    struct zoneFutureStat *zfs;
};

struct zfsMap
{
    int Level; 
    struct zfsIndex* idxs;
    struct zoneFutureStat* zfsArr;    
    struct zoneFutureStat* head, * tail;
    int distance;
    int missesInRound;

    uint32_t tracePos;
    int candidateZoneId;
    struct hash_table * incHashtb;

    int searchedCnt;
};
#define LOOKAHEAD 1024
extern struct hash_table *CacheBlkHashtb;
static struct zfsMap ZfsMapStack[LOOKAHEAD + 1];
struct EvictionInterval
{
    uint32_t zoneId;
    int ei;
};
struct EvictionInterval EvictionSerial [LOOKAHEAD];

static struct timeval tv_start, tv_stop;

static int IterCnt = 0;
static int CurrentRound = LOOKAHEAD; 
static uint32_t StopTracePos;
static int CurOptLevel = MAXTRACEMAPLEN;
uint64_t *TraceMAP;

// Functions for zfs. 
static void zfs_insertfront(struct zoneFutureStat * zfs, struct zoneFutureStat * target);
static int searchReverse(struct zfsMap * myMap);
static int init_zfsMap(int level);
static void free_zfsMap(int level);
static int isMissInAllRoundLevel(uint64_t tg_blk, int curRound);
static int oneWayScan(struct zfsMap* myMap);

int zoneopt_init()
{
    /* init page priv field. */
    struct cache_page *page = cache_rt.pages;
    for (uint64_t i = 0; i < STT.n_cache_pages; page++, i++)
    {
        page->priv = calloc(1, sizeof(struct page_payload));
        if (!page->priv)
            return -1;
    }

    global_evic_round = 0;

    char tracemap[128];
    sprintf(tracemap, "%s_%d", config_trace_seq_mmap_file_prefix, STT.traceId);
    int maxMapReq = MAXTRACEMAPLEN;
    
    int tracemapfd = open(tracemap, O_RDONLY);
    if (tracemapfd < 0)
    {
        // open trace file
        
        if ((tracemapfd = open(tracemap, O_RDWR | O_CREAT)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
        ftruncate(tracemapfd, sizeof(uint64_t) * maxMapReq);

        TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ | PROT_WRITE, MAP_SHARED, tracemapfd, 0);
        if (TraceMAP == (void *)-1)
        {
            log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }

        FILE *trace = fopen(TRACE_FILES[STT.traceId], "rt");
        if (trace == NULL)
        {
            exit(EXIT_FAILURE);
        };

        char action;
        uint64_t tg_blk;
        int mask;
        uint64_t *wrtReq = TraceMAP;
        uint64_t scanReqCnt = 0;
        while (!feof(trace)) // && scanReqCnt < STT.presetReq)
        {
            int ret;
#ifdef TRACE_SYSTOR17
            ret = fscanf(trace, "%c %d %lu\n", &action, &mask, &tg_blk);
#else
            ret = fscanf(trace, "%d %d %lu\n", &action, &mask, &tg_blk);
#endif

            if (ret < 0)
            {
                log_err_sac("error while reading trace file.");
                break;
            }

#ifdef TRACE_SYSTOR17
            tg_blk /= BLKSIZE;
#endif
            tg_blk += STT.start_Blkoff;

            if (action == ACT_WRITE && (STT.workload_mode & 0x02))
            {
                if ((tg_blk / N_ZONEBLK) > N_ZONES)
                {
                    log_info_sac("[warning] func:%s, target block overflow. \n", __func__);
                    continue;
                }

                *wrtReq = tg_blk;
                wrtReq++;
                scanReqCnt++;
            }
        }

        fclose(trace);
        msync(TraceMAP, sizeof(uint64_t) * maxMapReq, MS_SYNC);
        munmap(TraceMAP, sizeof(uint64_t) * maxMapReq);
        close(tracemapfd);
        // reopen
        if ((tracemapfd = open(tracemap, O_RDONLY)) < 0)
        {
            log_err_sac("Open TracefileMap failed: %s\n", strerror(errno));
            exit(EXIT_FAILURE);
        }
    }

    TraceMAP = mmap(NULL, sizeof(uint64_t) * maxMapReq, PROT_READ, MAP_SHARED, tracemapfd, 0);
    if (TraceMAP == (void *)-1)
    {
        log_err_sac("Create TraceMap failed: %s\n", strerror(errno));
        exit(EXIT_FAILURE);
    }

    return 0;
}

int zoneopt_login(struct cache_page *page, int op)
{
    // struct page_payload * p = (struct page_payload *)page->priv;
    // p->checked_round = 0;
    return 0;
}

int zoneopt_logout(struct cache_page *page, int op)
{
    return 0;
}

int zoneopt_hit(struct cache_page *page, int op)
{
    return 0;
}

int zoneopt_writeback_privi(int type)
{
    int ret, cnt = 0;
    struct page_payload *payload;

    if (type == FOR_READ)
        goto EVICT_CLEAN;
    else if (type == FOR_WRITE || type == FOR_UNKNOWN)
        goto EVICT_DIRTY;
    else
    {
        log_err_sac("[%s] error: MOST cache algorithm needs to be told eviction page type. \n", __func__);
        exit(EXIT_FAILURE);
    }

EVICT_CLEAN:
    log_err_sac("This offline algorithm doesn't support evicting clean block.");
    exit(EXIT_FAILURE);

EVICT_DIRTY:
    global_evic_round++;
    StopTracePos = STT.resetReqSeq > 0 ?  STT.presetReq + STT.resetReqSeq - 1 : STT.presetReq + STT.reqcnt_s - 1;
    ret = zoneopt_get_zone_out();
    return ret;
}

static int searchMaxEI_DFS(int thisRound)
{

    if(thisRound == 0)
        return 0;
    
    if(ZfsMapStack[thisRound-1].tracePos > StopTracePos){
        CurOptLevel = thisRound - 1;
        printf("Find New Depth [%d]: ", CurOptLevel);
        for(int i = 1; i < thisRound; i++){
            printf("[%d]->", ZfsMapStack[i].candidateZoneId);
        }
        printf("Done.\n");
        return 2; // new optimal path
    }
    
    if(thisRound == CurOptLevel){
        return -1;
    }
    
    if(thisRound > MaxLevel) {MaxLevel = thisRound;}
    
    int ret;
    int myLevelMaxSumEI = 0;
    // duplicate curZfsArray
    init_zfsMap(thisRound);
    struct zfsMap* myMap = &ZfsMapStack[thisRound];
    int levelInitTracePos = myMap->tracePos;

    // Progress Print
    IterCnt ++;
    if(IterCnt % 10000 == 0){
        for(int i = 1; i <= thisRound; i++){
            printf("[%.2f\%]->", (float)ZfsMapStack[i].searchedCnt / ZfsMapStack[i].distance);
        }
        Lap(&tv_stop);
        double time = TimerInterval_seconds(&tv_start, &tv_stop); 
        printf("%.2f(Sec)\n", time);
    }

    ret = oneWayScan(myMap);// 正向扫描至最大EI的Zone

    // continue run trace...
    int candidate_zoneId;
    while((candidate_zoneId = searchReverse(myMap)) >= 0){
        
        myMap->searchedCnt ++;

        myMap->candidateZoneId = candidate_zoneId;
        ret = searchMaxEI_DFS(thisRound + 1);
        if(ret > 0){ // new optimal path
            free_zfsMap(thisRound);
            return ret - 1; 
        } else if(ret < 0) {
            free_zfsMap(thisRound);
            return ret + 1; 
        } 
        //else {}
    }
    
    free_zfsMap(thisRound);
    return 0; 
}

// 正向扫描至最大EI的Zone
static int oneWayScan(struct zfsMap* myMap){
    uint64_t* wrtTgtBlk = TraceMAP + myMap->tracePos;
    struct zoneFutureStat * tmpZfs = myMap->tail;

    while(myMap->tracePos <= StopTracePos){
        
        int missed = isMissInAllRoundLevel(*wrtTgtBlk, myMap->Level);
        if(missed){
            // Add to map->incremental hashmap
            HashTab_Insert(myMap->incHashtb, *wrtTgtBlk,  1); 

            myMap->missesInRound ++;

            uint32_t belong_zoneId = *wrtTgtBlk / N_ZONEBLK;
            struct zoneFutureStat * zfs = myMap->idxs[belong_zoneId].zfs;
            
            zfs->increamentalBlks ++;
            // tuning the zfs ranked position in zfsArr
            if(zfs->releaseCnt >0 && zfs->releaseForMiss >= myMap->missesInRound){
                zfs->releaseForMiss ++;

                // 1) find the inserted position
                struct zoneFutureStat *insert_zfs = zfs;
                while (insert_zfs->pre != NULL && zfs->releaseForMiss > insert_zfs->pre->releaseForMiss)
                {
                    insert_zfs = insert_zfs->pre;
                }

                // 2) move
                if(insert_zfs != zfs && zfs == myMap->tail){
                    myMap->tail = myMap->tail->pre;
                }
                zfs_insertfront(zfs, insert_zfs);
                if(myMap->head->pre == zfs){
                    myMap->head = zfs;
                }
            }

        } else {
            uint64_t value;
            if(HashTab_Lookup(myMap->incHashtb, *wrtTgtBlk, &value) >= 0){
                HashTab_Update(myMap->incHashtb, *wrtTgtBlk, value + 1);
            }
        }
        
        while(myMap->missesInRound > tmpZfs->releaseForMiss){
            if(tmpZfs == myMap->head){
                myMap->tracePos ++;
                return 0;
            }
            tmpZfs = tmpZfs->pre;
        }

        wrtTgtBlk ++;
        myMap->tracePos ++;
    }

    // if end of the trace length
    return 1;
}

static int searchReverse(struct zfsMap * myMap){
    if(myMap->tracePos > StopTracePos)
        return myMap->head->zoneId;
    
    if(myMap->head == myMap->tail->next){
        return -1;
    }
    // build the map->tail zone eviction interval state
    int retZoneId = -1;

    if(myMap->missesInRound == myMap->head->releaseForMiss){
        retZoneId = myMap->head->zoneId;
        myMap->head = myMap->head->next;
        return retZoneId;
    }
    
    //逆向扫描
    while(myMap->head != myMap->tail->next){
        myMap->tracePos --;
        uint64_t * wrtTgtBlk = TraceMAP + myMap->tracePos;
        if(!isMissInAllRoundLevel(*wrtTgtBlk, myMap->Level - 1)){
            continue;
        }

        uint64_t hits;
        HashTab_Lookup(myMap->incHashtb, *wrtTgtBlk, &hits);
        if(hits > 1){
            HashTab_Update(myMap->incHashtb, *wrtTgtBlk, hits - 1);
             continue;
        } else {
            HashTab_Delete(myMap->incHashtb, *wrtTgtBlk);
            myMap->missesInRound --;
            
            uint32_t belong_zoneId = *wrtTgtBlk / N_ZONEBLK;
            struct zoneFutureStat * zfs = myMap->idxs[belong_zoneId].zfs;

            zfs->increamentalBlks--;
        }

        if(myMap->missesInRound == myMap->head->releaseForMiss){
            retZoneId = myMap->head->zoneId;
            myMap->head = myMap->head->next;
            return retZoneId;
        }
    }

    return -1;
}

static int zoneopt_get_zone_out()
{
    
    Lap(&tv_start);
    uint32_t from = 0, to = N_ZONEBLK - 1;


    init_zfsMap(0);
    searchMaxEI_DFS(1);
    Lap(&tv_stop);
    double time = TimerInterval_seconds(&tv_start, &tv_stop); 
    
    printf("ZONEOPT total time cost: %.2f\n", time);

    exit(EXIT_SUCCESS);

    int best_zoneId = EvictionSerial[CurrentRound].zoneId;

    // output write amplification.
    struct zbd_zone* z = zones_collection + best_zoneId;
    uint32_t rmw_scope = N_ZONEBLK - from;
    double wa = (double)rmw_scope / z->cblks_wtr;
    int canWalkTo = STT.resetReqSeq + STT.reqcnt_w + EvictionSerial[CurrentRound].ei - 1;

    log_info_sac("[%s] Zone[%d] WA: %.2f (%u/%u); expect EI: %ld, nextTracePos:%d\n", 
    __func__, z->zoneId, wa, rmw_scope, z->cblks_wtr, EvictionSerial[CurrentRound].ei, canWalkTo);

    // RMW
    //RMW(best_zoneId, from, to);

    CurrentRound ++;
    return best_zoneId;
}

static int compareByReleaseForMiss(const void *a, const void *b) //用来做比较的函数。
{
    return ((struct zoneFutureStat *)a)->releaseForMiss < ((struct zoneFutureStat *)b)->releaseForMiss;
}

static int isMissInAllRoundLevel(uint64_t tg_blk, int curRound){
    //log_info_sac("\ncheck hashtb: tgblk=%ld --> ", tg_blk);
    int i;
    int belong_zoneId = tg_blk / N_ZONES;
    for(i = curRound; i >= 0; i--){
        struct zfsMap * levelMap = &ZfsMapStack[i];
        if(i != curRound && belong_zoneId == levelMap->candidateZoneId){
            //log_info_sac("missed by ignore in level [%d]", i);
            return 1; // must miss
        }

        if(HashTab_Lookup(levelMap->incHashtb, tg_blk, NULL) >= 0){
            // hit
            //log_info_sac("hit in level [%d].", i);
            return 0;
        }
    }

    //log_info_sac("missed in all levels.");
    return 1; // missed
}

static void zfs_insertfront(struct zoneFutureStat * zfs, struct zoneFutureStat * target){
    if(target == NULL || zfs == NULL)
        return;

    if(target == zfs){
        return;
    }

    // take off zfs
    if(zfs->pre != NULL){ zfs->pre->next = zfs->next; }
    if(zfs->next != NULL) { zfs->next->pre = zfs->pre; }

    // insert in front of the target. 

    zfs->pre = target->pre;
    zfs->next = target;
    if (target->pre != NULL)
    {
        target->pre->next = zfs;
    }
    target->pre = zfs;
}

static int init_zfsMap(int level){
    if(level == 0){
        struct zfsMap* map = &ZfsMapStack[0];
        map->Level = level;
        map->idxs = NULL; // do not need to set idx
        map->tracePos = STT.resetReqSeq + STT.reqcnt_s ;
        map->incHashtb = CacheBlkHashtb;
        map->candidateZoneId = -1;
        map->head = map->tail = NULL;
        map->distance = 0;
        map->zfsArr = malloc(sizeof(struct zoneFutureStat) * N_ZONES);
        if(map->zfsArr == NULL){
            log_err_sac("%s: error", __func__);
            exit(EXIT_FAILURE);
        }

        struct zbd_zone *z = zones_collection;
        struct zoneFutureStat *zfs = map->zfsArr;
        for (int i = 0; i < N_ZONES; i++, z++, zfs++)
        {
            zfs->zoneId = z->zoneId;
            zfs->releaseCnt = z->cblks_wtr;
            zfs->releaseForMiss = z->cblks_wtr;
            zfs->increamentalBlks = 0;
        }

        return 0;
    }

    struct zfsMap* map = &ZfsMapStack[level];
    struct zfsMap* base = &ZfsMapStack[level - 1];
    map->Level = level;
    map->searchedCnt = 0;
    map->tracePos = base->tracePos;
    map->zfsArr = malloc(sizeof(struct zoneFutureStat) * N_ZONES);
    map->idxs = malloc(sizeof(struct zfsIndex) * N_ZONES);
    if(map->zfsArr == NULL || map->idxs == NULL){
        log_err_sac("%s: error", __func__);
        exit(EXIT_FAILURE);
    }

    struct zoneFutureStat* baseZfs = base->zfsArr;
    struct zoneFutureStat* genZfs = map->zfsArr;
    for(int i = 0; i < N_ZONES; i++, baseZfs++, genZfs++){
        genZfs->zoneId = baseZfs->zoneId;
        genZfs->releaseForMiss = 
            genZfs->releaseCnt = baseZfs->releaseCnt + baseZfs->increamentalBlks;
        genZfs->increamentalBlks = 0;

        // 剔除上一轮此候选Zone的配置
        if(genZfs->zoneId == base->candidateZoneId){
            genZfs->releaseForMiss = genZfs->releaseCnt = 0;
        }
    }



    qsort(map->zfsArr, N_ZONES, sizeof(struct zoneFutureStat), compareByReleaseForMiss);
    
    // link the zfsArr and build their indexes.
    genZfs = map->zfsArr;
    struct zoneFutureStat *pre = NULL;
    for(int i = 0; i < N_ZONES; i++, genZfs ++)
    {
        genZfs->pre = pre;
        if(pre != NULL)
            pre->next = genZfs;
        
        pre = genZfs;

        map->idxs[genZfs->zoneId].zfs = genZfs;
    }
    pre->next = NULL;

    map->head = map->zfsArr;
    map->tail = map->zfsArr + N_ZONES - 1;
    map->distance = N_ZONES - 1;
    map->missesInRound = 0;
    while(map->tail != NULL && map->tail->releaseForMiss == 0){
        map->tail = map->tail->pre;
        map->distance --;
    }

    HashTab_crt(STT.n_cache_pages * 4, &map->incHashtb);
    map->candidateZoneId = -1;

    return 0;
}

static void free_zfsMap(int level){
    struct zfsMap* map = &ZfsMapStack[level];
    free(map->idxs);
    free(map->zfsArr);
    HashTab_free(map->incHashtb);
    map->candidateZoneId = -1;
    map->tracePos  = 0;
}